/**
 * @author VernHe
 */
public class Solution_074 {
    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 3;
        System.out.println(searchMatrix(matrix, target));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 参数判断
        if (target < matrix[0][0] || target > matrix[m - 1][n - 1]) return false;
        // 确定所在行
        int row_index = search(matrix, target, m, n);
        System.out.println("目标数可能在第 " + (row_index + 1) + " 行中");
        // 行内二分查找
        int[] target_row = matrix[row_index];
        // 当前行中是否存在存在此数
        return isExist(target_row, target, n);
    }

    static int search(int[][] matrix, int target, int m, int n) {
        // 二分查找[begin,end) [0, 3) mid = 1,
        int begin = 0;
        int end = m;
        int mid_row = -1;
        // 找到target所在的行
        while (end > begin) {
            // 获取中间位置
            mid_row = (begin + end) >> 1;
            // 中间行
            int leftValue = matrix[mid_row][0];
            int rightValue = matrix[mid_row][n - 1];
            // 是否在中间行
            if (target >= leftValue && target <= rightValue) {
                return mid_row;
            }
            // 如果左半边
            if (target < leftValue) {
                end = mid_row;
            }
            // 如果是右半边
            if (target > rightValue) {
                begin = mid_row + 1;
            }
        }
        return mid_row;
    }

    /**
     * 目标数是否存中于指定的行中
     * @param row
     * @param target
     * @param length
     * @return
     */
    static boolean isExist(int[] row, int target, int length) {
        int begin = 0;
        int end = length;
        // 中间位置
        int mid;
        System.out.println("开始在行中查找......begin = " + begin + " end = " + end);
        while (end > begin) {
            System.out.println("begin = " + begin + ", end = " + end);
            mid = (begin + end) >> 1;
            int midValue = row[mid];
            if (midValue == target) {
                // 如果找到了
                return true;
            }
            if (target < midValue) {
                // 在左半边
                end = mid;
            }
            if (target > midValue) {
                // 在右半边
                begin = mid + 1;
            }
        }

        return false;
    }
}
